class Solution {
public:
    //分两种情况：
    //情况一：和最大的子数组刚好在数组的中间部分
    //情况二：和最大的子数组为数组的后部分加前部分
    //对于情况一，可以用普通的求最大子数组和方法求解
    //对于情况二：可以转换思路，既然后部分加前部分是最大的，说明数组中间那一部分是最小的，因此可以转换为求最小子数组和
    //最后需要考虑数组全为负数的情况
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp1(n + 1); //用于记录最大子数组和
        vector<int> dp2(dp1);   //用于记录最小子数组和

        int sum = 0;
        for (auto i : nums)
            sum += i;

        int max1 = INT_MIN, max2 = INT_MIN, dp2_min = INT_MAX;
        for (int i = 1; i < n + 1; i++)
        {
            dp1[i] = max(nums[i - 1], dp1[i - 1] + nums[i - 1]);
            max1 = max(max1, dp1[i]);

            dp2[i] = min(nums[i - 1], dp2[i - 1] + nums[i - 1]);
            max2 = max(max2, sum - dp2[i]);
            dp2_min = min(dp2_min, dp2[i]);
        }

        return dp2_min == sum ? max1 : max(max1, max2);
    }
};